#include <bits/stdc++.h>

template <typename T> T read() {
    T x = 0, f = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = ~f + 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
    return x * f;
}

const int N = 5e4 + 10, M = 2e6 + 10, INF = 2147483647; int n, m, a[N];

struct TREE {
    int l, r, val, key, size;
} tree[M]; int cnt;

inline unsigned int rnd() { static unsigned int x = 114; return (x *= 514) %= 998244353; }

struct FHQ_Treap {
    int root;

    int newnode(int val) { tree[++cnt] = {0, 0, val, rnd(), 1}; return cnt; }
    void update(int nw) { tree[nw].size = tree[tree[nw].l].size + tree[tree[nw].r].size + 1; return; }
    void split(int nw, int val, int &x, int &y) {
        if (!nw) return x = y = 0, void();
        if (tree[nw].val <= val) {
            x = nw; split(tree[nw].r, val, tree[x].r, y);
        }
        else {
            y = nw; split(tree[nw].l, val, x, tree[y].l);
        } update(nw); return;
    }
    int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (tree[x].key > tree[y].key) {
            tree[x].r = merge(tree[x].r, y); return update(x), x;
        }
        else {
            tree[y].l = merge(x, tree[y].l); return update(y), y;
        }
    }
    void ins(int val) { int x, y; split(root, val, x, y); root = merge(merge(x, newnode(val)), y); return; }
    void del(int val) { int x, y, z; split(root, val, x, z); split(x, val - 1, x, y); y = merge(tree[y].l, tree[y].r); root = merge(merge(x, y), z); }
    int getrank(int val) { int x, y; split(root, val - 1, x, y); int ans = tree[x].size + 1; root = merge(x, y); return ans; }
    int getnum(int rank) {
        int nw = root;
        while (rank) {
            if (tree[tree[nw].l].size + 1 == rank) return tree[nw].val;
            else if (tree[tree[nw].l].size >= rank) nw = tree[nw].l;
            else rank -= tree[tree[nw].l].size + 1, nw = tree[nw].r;
        }
        return tree[nw].val;
    }
    int pre(int val) {
        int x, y; split(root, val - 1, x, y); int nw = x;
        while (tree[nw].r) nw = tree[nw].r; int ans = nw ? tree[nw].val : -INF; root = merge(x, y); return ans;
    }
    int nxt(int val) {
        int x, y; split(root, val, x, y); int nw = y;
        while (tree[nw].l) nw = tree[nw].l; int ans = nw ? tree[nw].val : INF; root = merge(x, y); return ans;
    }
    void build(int l, int r) {
        for (int i = l; i <= r; i++) ins(a[i]); return;
    }
} tr[N << 2];

struct Segment_tree {
    int L[N << 2], R[N << 2];
    void build(int l, int r, int p = 1) {
        L[p] = l; R[p] = r; tr[p].build(l, r);
        if (l == r) return;
        int mid = l + r >> 1; build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1); return;
    }
    int queryrank(int l, int r, int val, int p = 1) {
        if (l <= L[p] && R[p] <= r) return tr[p].getrank(val) - 1;
        int mid = L[p] + R[p] >> 1; int ans = 0;
        if (l <= mid) ans += queryrank(l, r, val, p << 1);
        if (mid < r) ans += queryrank(l, r, val, p << 1 | 1); return ans;
    }
    int querynum(int l1, int r1, int rank) {
        int l = 0, r = 1e8; int ans = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (queryrank(l1, r1, mid) + 1 <= rank) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        return ans;
    }
    void update(int pos, int val, int p = 1) {
        tr[p].del(a[pos]); tr[p].ins(val);
        if (L[p] == R[p]) return;
        int mid = L[p] + R[p] >> 1;
        if (pos <= mid) update(pos, val, p << 1);
        else update(pos, val, p << 1 | 1); return;
    }
    int pre(int l, int r, int val, int p = 1) {
        if (l <= L[p] && R[p] <= r) return tr[p].pre(val);
        int mid = L[p] + R[p] >> 1; int ans = -INF;
        if (l <= mid) ans = std::max(ans, pre(l, r, val, p << 1));
        if (mid < r) ans = std::max(ans, pre(l, r, val, p << 1 | 1)); return ans;
    }
    int nxt(int l, int r, int val, int p = 1) {
        if (l <= L[p] && R[p] <= r) return tr[p].nxt(val);
        int mid = L[p] + R[p] >> 1; int ans = INF;
        if (l <= mid) ans = std::min(ans, nxt(l, r, val, p << 1));
        if (mid < r) ans = std::min(ans, nxt(l, r, val, p << 1 | 1)); return ans;
    }
} T;

int main() {
    n = read<int>(), m = read<int>();
    for (int i = 1; i <= n; i++) a[i] = read<int>(); T.build(1, n);
    while (m--) {
        int op = read<int>(), l = read<int>(), r = read<int>(), k; if (op != 3) k = read<int>();
        switch (op) {
            case 1: printf("%d\n", T.queryrank(l, r, k) + 1); break;
            case 2: printf("%d\n", T.querynum(l, r, k)); break;
            case 3: {
                T.update(l, r); a[l] = r; break;
            }
            case 4: printf("%d\n", T.pre(l, r, k)); break;
            default: printf("%d\n", T.nxt(l, r, k)); break;
        }
    } return 0;
}
//luogu P3380 二逼平衡树